import java.util.ArrayList;
import java.util.Arrays;

public class BinaryTree {
    public static void main(String[] args) {
        ArrayList<Character>preSeq=new ArrayList<>(
            Arrays.asList(new Character[]{'F','B','A','D','C','E','G','I','H'}));

        ArrayList<Character>inSeq=new ArrayList<>(
            Arrays.asList(new Character[]{'A','B','C','D','E','F','G','H','I'}));

        ArrayList<Character>postSeq=new ArrayList<>(
            Arrays.asList(new Character[]{'A','C','E','D','B','H','I','G','F'}));

        TreeNode root = new BinaryTree().buildBT(preSeq, inSeq);
        new BinaryTree().preorder(root);
    }   
    
    void preorder(TreeNode root){
        if(root == null) return;
        System.out.println(root.key);
        preorder(root.left);
        preorder(root.right);
    }

    void inorder(TreeNode root){
        if(root == null) return;
        inorder(root.left);
        System.out.println(root.key);
        inorder(root.right);
    }

    void postorder(TreeNode root){
        if(root == null) return;
        postorder(root.left);
        postorder(root.right);
        System.out.println(root.key);
    }

    //preSeq提供头节点的位置，inSeq提供头节点左右元素的个数
    TreeNode buildBT(ArrayList<Character> preSeq,ArrayList<Character> inSeq){
        //递归返回条件
        if(preSeq.size()==1){
            return new TreeNode(preSeq.get(0));
        }
        //preSeq提供头节点的位置
        TreeNode root = new TreeNode(preSeq.get(0));

        //按照头节点的位置分割inSeq
        //subList() 左闭右开
        ArrayList<Character> leftInSeq = new ArrayList<>(inSeq.subList(0,inSeq.indexOf(root.key)));
        ArrayList<Character> rightInSeq = new ArrayList<>(inSeq.subList(inSeq.indexOf(root.key)+1, inSeq.size()));

        //按照分割后inSeq的长度分割preSeq，目的是：为构建子树提供头节点
        ArrayList<Character> leftPreSeq = new ArrayList<>(preSeq.subList(1,1+leftInSeq.size()));
        ArrayList<Character> rightPreSeq = new ArrayList<>(preSeq.subList(1+leftInSeq.size(),preSeq.size()));

        //连接头节点和两个子树的头节点
        //递归
        //因为是创建了新的数组，并在新的数组上进行操作，所以必须完成连接操作
        //否则构建的子树无效
        if(leftPreSeq.size()>0 && leftInSeq.size()>0){
            root.left=buildBT(leftPreSeq,leftInSeq);
        }
        if(rightPreSeq.size()>0 && rightInSeq.size()>0){
            root.right=buildBT(rightPreSeq,rightInSeq);
        }
        return root;
    }
}

class TreeNode{
    char key;
    TreeNode left;
    TreeNode right;
    public TreeNode(char key){
        this.key=key;
        left=right=null;
    }
}
